package uestc.lj.basicPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/11/28
 */
public class Code04_HorseJump {
	public static int getWays(int x, int y, int k) {
		return process(x, y, k);
	}

	/**
	 * 从(0,0)出发到(x,y)，必须跳step步
	 *
	 * @param x
	 * @param y
	 * @param step
	 * @return
	 */
	private static int process(int x, int y, int step) {
		if (x < 0 || x > 8 || y < 0 || y > 9) {
			return 0;
		}
		if (step == 0) {
			return (x == 0 && y == 0) ? 1 : 0;
		}
		return process(x - 1, y + 2, step - 1) + process(x + 1, y + 2, step - 1)
				+ process(x + 2, y + 1, step - 1) + process(x + 2, y - 1, step - 1)
				+ process(x + 1, y - 2, step - 1) + process(x - 1, y - 2, step - 1)
				+ process(x - 2, y - 1, step - 1) + process(x - 2, y + 1, step - 1);
	}


	public static int dpGetWays(int x, int y, int step) {
		if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {
			return 0;
		}
		int[][][] dp = new int[9][10][step + 1];
		dp[0][0][0] = 1;
		for (int h = 1; h <= step; h++) {
			for (int row = 0; row < 9; row++) {
				for (int col = 0; col < 10; col++) {
					dp[row][col][h] += getValue(dp, row - 1, col + 2, h - 1);
					dp[row][col][h] += getValue(dp, row + 1, col + 2, h - 1);
					dp[row][col][h] += getValue(dp, row + 2, col + 1, h - 1);
					dp[row][col][h] += getValue(dp, row + 2, col - 1, h - 1);
					dp[row][col][h] += getValue(dp, row + 1, col - 2, h - 1);
					dp[row][col][h] += getValue(dp, row - 1, col - 2, h - 1);
					dp[row][col][h] += getValue(dp, row - 2, col - 1, h - 1);
					dp[row][col][h] += getValue(dp, row - 2, col + 1, h - 1);
				}
			}
		}
		return dp[x][y][step];
	}

	public static int getValue(int[][][] dp, int row, int col, int step) {
		if (row < 0 || row > 8 || col < 0 || col > 9) {
			return 0;
		}
		return dp[row][col][step];
	}
}
